/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-10-05
 * Time: 23:00
 */
public class Solution {
    public static void mergeSort(int[] arr) {
        merge(arr,0,arr.length-1);
    }
    //核心操作
    private static void merge(int[] arr,int left,int right) {
        //分解
        if (left >= right) {
            return;
        }
        int mid = (left+right)/2;
        merge(arr,left,mid);
        merge(arr,mid+1,right);

        //开始合并
        Merger(arr,left,mid,right);
    }
    //合并操作
    private static void Merger(int[] arr,int left,int mid,int right) {
        int[] tmp = new int[right-left+1];
        int k = 0;

        int as = left;
        int ae = mid;

        int bs = mid+1;
        int be = right;

        while (as <= ae && bs <= be) {
            if (arr[as] <= arr[bs]) {
                tmp[k] = arr[as];
                k++;
                as++;
            }else {
                tmp[k] = arr[bs];
                k++;
                bs++;
            }
        }

        while (as <= ae) {
            tmp[k] = arr[as];
            k++;
            as++;
        }

        while (bs <= be) {
            tmp[k] = arr[bs];
            k++;
            bs++;
        }

        for (int i = 0; i < k; i++) {
            arr[i+left] = tmp[i];
        }
    }

}
